﻿/*
 * Copyright (c) Jason Paul Morley, 2010
 * Licensed under the MIT license: http://www.opensource.org/licenses/mit-license.php
 */

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Algorithms
{
    /// <summary>
    /// Generates a solution to Dijkstra's algorithm
    /// </summary>
    public class Dijkstras : Core.BComponent
    {
        private bool OnGenerate(Core.Event.GenerateSolution e)
        {
            Run(e.StartNode);
            return Core.EventMap.ContinueEvent;
        }

        /// <summary>
        /// Build the algorithm class
        /// </summary>
        /// <param name="em"></param>
        /// <param name="db"></param>
        public Dijkstras(Core.EventMap em, Core.Database db) : base(em, db)
        {
            em.Bind<Core.Event.GenerateSolution>(OnGenerate, Core.Event.GenerateSolution.EventName);
            UpdateDatabase();
        }

        /// <summary>
        /// The data dijkstra's keeps about a node
        /// </summary>
        private class NodeData
        {
            public NodeData() {  previous = null; visited = false; }
            public Core.Node previous;
            public bool visited;
        }

        /// <summary>
        /// The data stored for each node
        /// </summary>
        private Dictionary<string, NodeData> StoredData = new Dictionary<string, NodeData>();

        /// <summary>
        /// Get the data stored about the node
        /// </summary>
        /// <param name="n"></param>
        /// <returns></returns>
        private NodeData GetData(Core.Node n)
        {
            if (StoredData.ContainsKey(n.id)) return StoredData[n.id];
            else throw new Core.Error("Dijkstra", "GetData(" + n.id + ")", "Invalid node: " + n.id + " was not in database");
        }

        /// <summary>
        /// Update the extra data stored on the database
        /// </summary>
        public void UpdateDatabase()
        {
            StoredData.Clear();
            foreach (Core.Node n in Database.Nodes)
                StoredData[n.id] = new NodeData();
        }

        /// <summary>
        /// Get the node with the minimum distance
        /// </summary>
        /// <returns></returns>
        protected Core.Node GetMinDistance(List<Core.Node> k)
        {
            double distance = double.PositiveInfinity;
            Core.Node r = null;
            foreach (Core.Node n in k)
            {
                NodeData data = GetData(n);
                Core.Debug.Log("Dijkstra", "GetMinDistance()",
                                n.id + ".distance=" + n.distance.ToString()  + ", "
                                + n.id + ".visited=" + data.visited.ToString() + "," 
                                + "Current active: " + (r == null ? "null" : r.id));
                if (!data.visited)
                {
                    if (n.distance < distance)
                    {
                        distance = n.distance;
                        r = n;
                    }
                }
            }
            Core.Debug.Log("Dijkstra", "GetMinDistance()", "Minimum node selected: " + (r == null ? "null" : r.id));
            return r;
        }

        /// <summary>
        /// Get if the passed node was visited by the algorithm
        /// </summary>
        /// <param name="n"></param>
        /// <returns></returns>
        protected bool WasVisited(Core.Node n)
        {
            return GetData(n).visited;
        }

        /// <summary>
        /// Update the distance of the neighbours of the node
        /// </summary>
        /// <param name="u">The node whose neighbours to update</param>
        protected void UpdateNeighbours(Core.Node u)
        {
            List<Core.Node> neighbours = Database.GetConnected(u);
            foreach (Core.Node n in neighbours)
            {
                NodeData data = GetData(n);

                if (!data.visited)
                {
                    Core.Edge j = Database.GetJoiningEdge(u, n);
                    if (j == null)
                        throw new Core.Error("Dijkstra", "UpdateNeighbours(" + u.id + ")", "Edges " + u.id + " and " + n.id + " are not connected");
                    Database.Steps.Add(new Steps.ConsiderEdge(n, j));

                    double newDistance = j.distance + u.distance;
                    Core.Debug.Log("Dijkstra", "UpdateNeighbours(" + u.id + ")", "calculates distance for node " + n.id + " as " + newDistance.ToString());

                    if (n.distance > newDistance)
                    {
                        Database.Steps.Add(new Steps.AssignNode(n, newDistance));
                        n.distance = newDistance;
                        Core.Debug.Log("Dijkstra", "UpdateNeighbours(" + u.id + ")", "reassigns distance for " + n.id + " to " + newDistance.ToString());
                    }
                    data.previous = u;
                }
                else
                    Core.Debug.Log("Dijkstra", "UpdateNeighbours(" + u.id + ")", "ignores visited node " + n.id);
            }
        }

        /// <summary>
        /// Run the algorithm using the passed node as the starting node
        /// </summary>
        /// <param name="start"></param>
        public void Run(Core.Node start)
        {
            UpdateDatabase();

            start.distance = 0;
            Database.Steps.Add(new Steps.AssignNode(start, 0));
            List<Core.Node> toProcess = new List<Core.Node>(Database.Nodes);

            while (toProcess.Count > 0)
            {
                Core.Node u = GetMinDistance(toProcess);
                if (u == null) break;
                Core.Debug.Log("Dijkstra", "Generate(" + start.id + ")", "selects node " + u.id);
                Database.Steps.Add(new Steps.VisitNode(u));

                GetData(u).visited = true;
                Core.Debug.Log("Dijkstra", "Generate(" + start.id + ")", "marks node " + u.id + " as visited");
                toProcess.Remove(u);

                UpdateNeighbours(u);
                Core.Debug.Log("Dijkstra", "Generate(" + start.id + ")", toProcess.Count.ToString() + " nodes unprocessed");
            }
            Database.Steps.Add(new Steps.Finish());
        }
    }
}
